The present invention relates to a decoding apparatus and a decoding method for soft decision decoding of a low density parity check code (LDPC), and to an information processing method and an information processing apparatus employing the decoding apparatus.
The low density parity code, referred to below as LDPC code, is a sort of a linear code, publicized in 1962 by Robert G. Gallager, and is featured by the fact that the number of non-zero elements of the parity check matrix is small as compared to the total number of the elements, that is that the non-zero elements of the parity check matrix is low in density (see the Non-Patent Publication 1, indicated below).
It is also known that, since no short cycles are contained in a bipartite graph of the parity check matrix, the LDPC code exhibits satisfactory bit error characteristics.
In a communication channel suffering from noise or erasure, it is customary to use error correction codes in which an information word may be estimated correctly on the receiving side. FIG. 23 shows an example of a communication system employing the LDPC code. Referring to FIG. 23, a communication apparatus 200 includes an LDPC encoding unit 201 for generating an LDPC code from an information word (message), a communication channel 202 for transmitting the codeword, and an LDPC decoding unit 203 for receiving a word from the communication channel 202 to decode the code.
The transmitting side LDPC codes the information word to send the resulting codes to the communication channel 201. The receiving side receives a signal, including the noise added on the communication channel 201, and decodes the received signal by an encoding rule used on the transmitting side to estimate the information word. In case the LDPC code is used, iterative decoding employing the soft decision information is usually carried out. The iterative decoding, employing the soft decision information, is carried out, for example, in the turbo code having properties similar to those of the LDPC code.
The LDPC code may be applied not only to the above communication system but also to a recording and/or reproducing channel. FIG. 24 depicts a block diagram showing a recording and/or reproducing system 210 employing the LDPC code. Referring to FIG. 24, the recording and/or reproducing system 210 includes an LDPC encoding unit 211 for generating an LDPC code from a message, such as music or pictures, a recording and/or reproducing system unit 212 for channel-encoding and recording the LDPC codes generated and reading out and channel-decoding the signals recorded, and an LDPC decoding unit 213 for detecting codes from the channel-decoded data. The data, having the codes detected by the LDPC decoding unit 213, are decoded into messages.
That is, the information words are LDPC encoded, during the recording, and recorded on a recording medium. During the reproduction, the signals, corrupted with the noise, are read out from the recording medium and channel detection responsive to inter-symbol interference of the channels and channel decoding are carried out as necessary, followed by decoding, based on the LDPC encoding rule used during the recording, to estimate the information word.
The LDPC code, used in, for example, the communication system or the recording and/or reproducing system, is now explained in detail. With a parity check matrix H of a parity check matrix, having M rows and N columns, an optional codeword vector c of an LDPC code, with a code length N, satisfies the following equation (1):Hc=0  (1)
where H is an M-row N-column parity check matrix.
This equation (1) represents M parity check equations. If the rank of H is given by (N−K), where K is a dimension, the code rate of the LDPC codes is given by K/N. In case M>N−K, it indicates that there is a redundant parity check equation.
FIG. 1 shows an example of a parity check matrix of the binary LDPC code. This 7-row 21-column matrix has a rank equal to 6, and the code thereby determined is a linear code with a code length N=21 and with a dimension K=15. In this matrix, the number of non-zero elements in each row (number of “1”s) (Hamming weight) Wc is unexceptionally 6, while the number of non-zero elements in each column (number of “1”s) (Hamming weight) Wc is unexceptionally 2. The LDPC code having a parity check matrix with uniform Wc is called a regular LDPC code.
The LDPC code is a linear code and is not limited to binary codes. That is, the same discussions may be made for cases other than the binary code. However, in the following explanation, the case of a binary code is unexceptionally taken as an example.
In the above-described communication system or recording and/or reproducing system, the information word (message) is LDPC-coded for detecting the codes by the parity check matrix in the LDPC decoding unit 203 or in the LDPC decoding unit 213 in the LDPC encoding unit 201 or in the LDPC encoding unit 211. For obtaining the LDPC code, a K-row N-column generator matrix G (satisfying GHT=0) is first found from an M-row N-column K-dimensional parity check matrix H. An N-bit codeword ((m0m1 . . . mk−1)G=(c0c1 . . . cN−1) may be obtained by multiplying a K-bit binary message (m0m1 . . . mk−1) with the generator matrix G. The codeword, thus obtained, is transmitted via a modulator to a communication channel and received as a received signal by the receiving side. This received signal is demodulated and then decoded by the parity check matrix so as to be output as an estimated value of the transmitted message K bits (m0^m1^ . . . mk−1^) where ^ indicates a hat, hereinafter the same.
The code detecting method for detecting the code from the received signal is now explained. It is known that the LDPC codes may be code-detected by a message passing algorithm, based on a parity check matrix or on a bipartite graph. The bipartite graph, representing the M-row N-column parity check matrix, is made up by M nodes, associated with the check, N nodes (variable nodes) associated with variables, and edges interconnecting the nodes. The edges are associated with the sites of non-zero elements of the parity check matrix, such that the n'th check nodes and the n'th variable nodes are interconnected at the edges only when the element of the n'th row and the n'th column is not zero. Since the case of the binary code is here explained, the variable node is expressed hereinbelow as a bit node.
FIG. 2 shows a bipartite graph associated with the parity check matrix of FIG. 1. The graph is made up by seven check nodes Xm (X0 to X6), represented by circles (◯), and by 21 bit nodes Yn (Y0 to Y20), represented by squares (□). To each check node Xm, there are connected six edges, whereas to each bit node Yn, there are connected two edges.
The LDPC codes may be decoded by an SISO (Soft-In Soft-Out) decoding method by the message passing algorithm or the sum-product algorithm, in which a message is propagated between the check node Xm and the bit node Yn, interconnected by an edge, and iterating message exchanges from the bit node Xm to the check node Yn and from the check node Yn to the bit node Xm. This message passing algorithm may be carried out by iterating the following sequential operations:
[1] Operation 0—Initializing
For all edges, emanating from the respective bit nodes Yn, the messages q0m,n and q1m,n, propagated from the bit node Yn to the check node Xm, are initialized with the priori probability p0n, p1n. It is noted that pxn denotes the priori probability for the bit n being “x”.
[2] Operation 1—Processing at the Check Modes
For the totality of the edges, emanating from the check nodes Xm, the messages r0m,n and r1m,n, propagated from the check node Xm to the bit node Yn, are found in accordance with the following equations:
                              r                      m            ,            n                    0                =                              1            +                                          ∏                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                                          \                      ⁢                      n                                                                                  ⁢                              (                                                      q                                          m                      ,                                              n                        ′                                                              0                                    -                                      q                                          m                      ,                                              n                        ′                                                              1                                                  )                                              2                                    (                  2          ⁢                      -                    ⁢          1                )                                          r                      m            ,            n                    1                =                              1            -                                          ∏                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                                          \                      ⁢                      n                                                                                  ⁢                              (                                                      q                                          m                      ,                                              n                        ′                                                              0                                    -                                      q                                          m                      ,                                              n                        ′                                                              1                                                  )                                              2                                    (                  2          ⁢                      -                    ⁢          2                )            
where N(m): the column numbers of non-zero elements in an n'th column of the parity check matrix
X\y: set obtained on eliminating elements y from a set X.
[3] Operation 2—Processing in a Bit Node
The posteriori probability of the respective bits q0n and q1n of the respective bits are found as necessary from the following equation:
                              q          n          0                =                              a            n                    ⁢                      p            n            0                    ⁢                                          ⁢                                    ∏                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                        ⁢                          r                              m                ,                n                            0                                                          (                  3          ⁢                      -                    ⁢          1                )                                          q          n          1                =                              a            n                    ⁢                                          ⁢                      p            n            1                    ⁢                                          ⁢                                    ∏                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                        ⁢                          r                              m                ,                n                            1                                                          (                  3          ⁢                      -                    ⁢          2                )            
where
M(n): column numbers of non-zero elements in an n'th column of the parity check matrix
an: normalizing constant for setting q0n+q1n=1.
In case further iterations are needed, the messages propagated from the bit node Yn to the check node Xm are calculated in accordance with the following equations:
                              q                      m            ,            n                    0                =                              a                          m              ,              n                                ⁢                      p            n            0                    ⁢                                          ⁢                                    ∏                                                m                  ′                                ∈                                                      M                    ⁡                                          (                      n                      )                                                        ⁢                  \                  ⁢                  m                                                      ⁢                          r                                                m                  ′                                ,                n                            0                                                          (                  4          ⁢                      -                    ⁢          1                )                                          q                      m            ,            n                    1                =                              a                          m              ,              n                                ⁢                      p            n            1                    ⁢                                          ⁢                                    ∏                                                m                  ′                                ∈                                                      M                    ⁡                                          (                      n                      )                                                        ⁢                  \                  ⁢                  m                                                      ⁢                          r                                                m                  ′                                ,                n                            1                                                          (                  4          ⁢                      -                    ⁢          2                )            
where
am,n: normalizing constant for setting q0m,n+q1m,n=1.
With regard to the decoding by the message passing algorithm, the operations 1 and 2 are iterated until the conditions for termination are met and, ultimately, the information word is estimated by hard decision decoding. Customarily, the conditions for termination are:
1) that the number of times of iteration has reached the preset value; and
2) that, if the number of times of iteration has not reached the preset value, but the result of hard decision has satisfied the parity check condition. The parity check is represented by the following equation (5):
If the result of hard decision: ĉthe parity check:Hĉ=0  (5)
Meanwhile, ĉ (c hat) is also described by c^ in the following explanation.
As a calculating method, equivalent to the above algorithm, the operations of multiplication may be replaced in their entirety by the addition by conversion into calculating expressions in the log domain by employing the log likelihood ratio (LLR), thereby simplifying the processing by hardware or software. The algorithm for calculations in the log domain is as follows:
[1] Operation 0—Initializing
For the totality of the edges, emanating from the respective bit nodes Yn, the messages Qm,n propagating the edges are initialized by the priori log likelihood Pn of the respective bits. It is noted that the messages Qm,n propagating the edges and the priori log likelihood Pn of the respective bits are defined as in the following equations (6-1) and (6-2), respectively:Qm,n≡ln(q0m,n/q1m,n)  (6-1)Pn≡ln(p0n/p1n)  (6-2)
[2] Operation 1—Processing
For the totality of edges, emanating from the check nodes Xm, the messages Rm,n, propagating the edges, are calculated by the following equation (7-1), where Am, Bm and the message Rm,n are defined as shown by the equations (7-2) to (7-4) and the functions f, g, αm,n and βm,n are represented by the following equations (7-5) to (7-8):
                              R                      m            ,            n                          =                              (                                          ∏                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                                          \                      ⁢                      n                                                                                  ⁢                              α                                  m                  ,                                      n                    ′                                                                        )                    ⁢                                          ⁢                      g            (                                          ∑                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                                          \                      ⁢                      n                                                                                  ⁢                              f                ⁡                                  (                                      B                                          m                      ,                                              n                        ′                                                                              )                                                      )                                                                                                        ⁢                  =                                    (                                                A                  m                                /                                  α                                      m                    ,                    n                                                              )                        ⁢                                                  ⁢                          g              ⁡                              (                                                      B                    m                                    -                                      f                    ⁡                                          (                                              β                                                  m                          ,                          n                                                                    )                                                                      )                                                                                                                  A          m                ≡                              ∏                                          n                ′                            ∈                              N                ⁡                                  (                  m                  )                                                              ⁢                      α                          m              ,                              n                ′                                                                        (                  7          ⁢                      -                    ⁢          2                )                                          B          m                ≡                              ∑                                          n                ′                            ∈                              N                ⁡                                  (                  m                  )                                                              ⁢                      f            ⁡                          (                              β                                  m                  ,                                      n                    ′                                                              )                                                          (                  7          ⁢                      -                    ⁢          3                )            messages Rm,n≡ln(r0m,n/r1m,n)  (7-4)
                              f          ⁡                      (            x            )                          =                              ln            ⁢                                                  ⁢                                                            ⅇ                  x                                +                1                                                              ⅇ                  x                                -                1                                              =                                    -              ln                        ⁢                                                  ⁢            tanh            ⁢                                                  ⁢                          (                              x                /                2                            )                                                          (                  7          ⁢                      -                    ⁢          5                )            g(x)=−ln tan h(x/2):inverse function of function f  (7-6)αm,n:code part of Qm,n  (7-7)βm,n:absolute value of Qm,n  (7-8)
[3] Operation 2—Processing in the Bit Node
The posterior log likelihood Qn of each bit, defined by the following equation (8):Qn≡ln(q0n/q1n)  (8)
is found from the following equation (9):
posteriori value:
                              Q          n                =                              P            n                    +                                    ∑                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                        ⁢                          R                              m                ,                n                                                                        (        9        )            
In case further iterations are necessary, the messages Qm,n, propagated from the bit node Yn to the check node Xm are calculated in accordance with the following equation (10):
                              Q                      m            ,            n                          =                                            P              n                        +                                          ∑                                                      m                    ′                                    ∈                                                            M                      ⁡                                              (                        n                        )                                                              ⁢                    \                    ⁢                    m                                                              ⁢                              R                                                      m                    ′                                    ,                  n                                                              =                                    Q              n                        -                          R                              m                ,                n                                                                        (        10        )            
A specified example of a decoding device, configured for decoding the LDCP codes by iterating the calculations of the above operations 1 and 2, is now explained. FIG. 25 depicts a block diagram showing a decoding device described in the Non-Patent Publication 2 by T. Zhang et al.
Referring to FIG. 25, the decoding device 300 is made up by a memory 301, in which to store the priori values, a bit node processing calculating unit 302 for carrying out calculations in the bit node Yn, a check node processing calculating unit 303 for carrying out calculations in the check node Xm, a memory 304 in which to store messages Rm,n from the bit node Yn to the check node Xm and from the check node Xm to the bit node Yn, and a hard decision decoder 305 for carrying out hard decision decoding responsive to the result of the bit node processing calculating unit 302 to output an estimated information word. This decoding device 300 uses the same calculating unit for each iteration and each calculating unit performs processing of multiple nodes time-divisionally.
The decoding device 300 is supplied with replay signals or received signals, corrupted with noise, which are saved in the memory 301 adapted to store priori values. The messages are iteratively propagated, via memory 304 for message storage, between the bit node processing calculating unit 302 for carrying out the processing of the above operation 2, and the check node processing calculating unit 303 for carrying out the processing of the above operation 1. Ultimately, the hard decision decoder 305 performs hard decision decoding to estimate the information word. It is noted that the initializing operations and the decision unit for deciding on the condition for terminating the repetitions are omitted for simplicity.
The configuration of a check node processing calculating unit 303 for reading out the message Qm,n from the bit node Yn to the check node Xm, from the memory 304, and for calculating the message Rm,n to be transferred from the check node Xm to the bit node Yn, is specifically explained.
FIG. 26 depicts a circuit diagram showing an example of major parts of a check node processing calculating unit. Here, an example of a calculating unit corresponding to the check of the first row of the parity check matrix shown in FIG. 1, is specifically shown.
In FIG. 26, a check node processing calculating unit 400 includes a converter 401t (4010 to 4015 in FIG. 26) for transforming absolute values βm,n of the message Qm,n at a corresponding location to a function f, an adder 402 for finding Bm, representing the sum thereof, shown in the equation (7-3), an adder 403t for finding the difference from the function f obtained from the messages Qm,n, corresponding to Bm, a converter 404t for transforming an output of the adder 403t into a function g, a multiplier 407 for multiplying the totality of codes αm,n of the message Qm,n to find Am shown in the above equation (7-2), a multiplier 406t for multiplying an output (Am) of the multiplier 407 with the code αm,n of the corresponding message Qm,n, and a multiplier 405t for multiplying the outputs of the converters 404t and 406t to output the message Rm,n.
It is noted that the function f, used in finding the message Rm,n from the check node Xm to the bit node Yn, is a function for converting a log likelihood ratio |ln(q0m,n/q1m,n)| into −ln|q0m,n−q1m,n|. The function g is an inverse transform of the function f and is a function of converting −ln|r0m,n−r1m,n| into a log likelihood ratio |ln(r0m,n/r1m,n)|. The functions f and g are of complex form inclusive of a hyperbolic function or a log function and, thus are implemented in many cases by approximate values. In case the LDPC codes are decoded on a circuit or by software, it is customary to limit the values that can be assumed by a message to a finite number of discrete values.
In the Patent Publication 1, for example, recited below, fQ(x), in which as-converted values are represented by a finite number of discrete values, is defined, as an approximation of the function f(x), as shown by the following equation (11):
                                          f            Q                    ⁡                      (            x            )                          =                  {                                                                      5.00                  ,                                                                              0                  ≤                  x                  ≤                  0.10                                                                                                      2.25                  ,                                                                              0.10                  ≤                  x                  ≤                  0.35                                                                                                      1.50                  ,                                                                              0.35                  ≤                  x                  ≤                  0.60                                                                                                      1.00                  ,                                                                              0.60                  ≤                  x                  ≤                  0.90                                                                                                      0.75                  ,                                                                              0.90                  ≤                  x                  ≤                  1.20                                                                                                      0.50                  ,                                                                              1.20                  ≤                  x                  ≤                  1.60                                                                                                      0.30                  ,                                                                              1.60                  ≤                  x                  ≤                  2.30                                                                                                      0.10                  ,                                                                              2.30                  ≤                  x                                                                                        (        11        )            
As a method for implementing fQ(x), indicated by this equation (11), it may be considered to formulate a table for fQ(x), with all values that may be assumed by x as indices, in the above converter 401t, and to output fQ(x), corresponding to x, obtained on having reference to this table (=absolute value βm,n of the message Qm,n). It also may be considered to find which domain x belongs to and to output a corresponding value, as now explained.
FIG. 27 depicts a circuit diagram showing an example of a converter outputting fQ(x) from an input x. A converter 410 includes comparators 4110 to 4116 for determining whether the value of x given is not larger than 0.1, 0.35, 0.60, 0.90, 1.2, 1.6 or 2.3, respectively, AND gates 4121 to 4126 for outputting an AND of the decision value of the comparator 411 and inverted values of decision values of the preceding stages, a NOT gate 415 for inverting a decision value of a comparator 4116 of the last stage, and a selection circuit 416, supplied with outputs of the comparator 4110 of the foremost stage, AND gates 4121 to 4126 and the NOT gate 415 to select fQ(x) depending on these outputs. Thus, it is first determined to which of the eight ranges of the equation (11) belongs x, and the selection circuit 416 then selects the value of fQ(x) based on the results to output the value indicating the so selected value.
[Non-Patent Publication 1] R. C. Gallager, ‘LDCP codes (Low Density parity Check Codes)’, MIT Press, 1963,
[Non-Patent Publication 2] T. Zhang and K. K. Parhi, ‘A 54 MBP (3,6)—REGULAR FPGA LDPC DECODER’, IEEE Workshop on Signal Processing Systems', 2002, pp 127 to 132.
[Patent Publication] Japanese Laid-Open Patent publication 2002-118474
However, the method for transforming a function f and for inverse transform g in a check node processing calculating unit, consisting in formulating fQ(x) in a table, with all values that can be assumed by x, as indices, and in storing the table in a ROM or in an array for reading out later, suffers a problem that, since the table becomes longer as the unit of quantization for x becomes smaller, the ROM or the array as needed becomes larger. If, on the other hand, it is determined which is the range of x by the circuit shown in FIG. 27, the number of the comparators 411t is increased with the number of the domains of x (eight in the case of fQ(x) shown in the above equation (11)), while the configuration of the selection circuit 416, selecting an output value, becomes complex. The function g, given by the same function as the function f, suffers from a similar problem